from typing import List

WHITE = 0
GRAY = 1

IN_ORDER = 0
PRE_ORDER = 1
POST_ORDER = 2
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def travesal(self, root: TreeNode, order = IN_ORDER) -> List[int]:
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None:
                continue
            if color == WHITE:
                if order == IN_ORDER:
                    stack.append((WHITE, node.right))
                    stack.append((GRAY, node))
                    stack.append((WHITE, node.left))
                elif order == PRE_ORDER:
                    stack.append((WHITE, node.right))
                    stack.append((WHITE, node.left))
                    stack.append((GRAY, node))
                elif order == POST_ORDER:
                    stack.append((GRAY, node))
                    stack.append((WHITE, node.right))
                    stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res


root = TreeNode(1)
tn1 = TreeNode(2)
tn2 = TreeNode(3)
root.right = tn1
tn1.left = tn2

print(Solution().travesal(root, IN_ORDER))
print(Solution().travesal(root, PRE_ORDER))
print(Solution().travesal(root, POST_ORDER))


